COMMENT ⊗   VALID 00009 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input basic
C00003 00003	\area {Theory of Computation}
C00009 00004	\area {Artificial Intelligence}
C00016 00005	\area {Systems}
C00020 00006	\area {Hardware}
C00023 00007	\area {Analysis of Algorithms}
C00031 00008	\area {Numerical Analysis}
C00039 00009	\par\vfill\eject
C00040 ENDMK
C⊗;
\input basic
\def\problem#1(#2){\vskip 20pt\penalty 1000
\hjust{\advcount1\count1.\hskip 6pt{\bf #1}(#2 points)}
\penalty 1000
\vskip 10pt}

\def\boxit#1{\vjust{\hrule\hjust{\vrule\hskip 3pt
	\vjust{\vskip 3pt #1\vskip 3pt}\hskip 3pt\vrule}\hrule}}

\def\pan{\par\vskip 7pt\noindent}

\def\area#1{\setcount1 0\par\vfill\eject
\hjust to size{\hfill{\bf #1}\hfill}}

\def\bline{\par\vskip 10pt}
\def\tline{\par\vskip 20pt}
\def\hline{\par\vskip  5pt}


\def\indent(#1){\hangindent 40pt\noindent\hjust to 40pt{\hskip 20pt(#1)\hfill}\!}
\def\part(#1){\noindent\hjust to 20pt{(#1)\hfill}\!}

\area {Theory of Computation}

\problem Turing (5)

\noindent
(a) Why did A. M. Turing invent the ``Turing machine''?
\bline
\noindent
(b) Did he spend more years of his life working with abstract ``Turing machines''
or with real computers?\ \ (Give some background information to support your
answer.)

\problem Resolution and Unification (7)

Prove by resolution that the following set of clauses is unsatisfiable.
\bline
$P(g(x,y),x,y)$
\bline
$¬P(x,y,u) ∨ P(y,z,v) ∨ ¬P(x,v,w) ∨ P(u,z,w)$
\bline
$¬P(k(x),x,k(x))$

\problem Sorted Languages (18)

Consider strings over an alphabet $\{a↓1,\ldotss,a↓m\}$ whose letters are
linearly ordered: $a↓1<\cdots<a↓m$. If $\alpha=x↓1x↓2\ldotsm x↓n$ is
a string, let sorted$(\alpha)$ be the string $x↓{p↓1}x↓{p↓2}\ldotsm x↓{p↓n}$,
where $p↓1p↓2\ldotsm p↓n$ is a permutation of $\{1,2,\ldotss,n\}$ and
$x↓{p↓1}<x↓{p↓2}<\cdots<x↓{p↓n}$.

If $L$ is a language over $\{a↓1,\ldotss,a↓m\}$, define new languages
as follows:
$$\baselineskip 15pt\eqalign 
{\hjust{sortedsubset}(L) 
	⊗= \leftset\alpha\in L\relv \alpha=\hjust{sorted}(\alpha)\rightset;\cr
\hjust{sorted}(L) 
	⊗= \leftset\hjust{sorted}(\alpha)\relv\alpha\in L\rightset;\cr
\hjust{unsorted}(L) 
	⊗= \leftset\alpha\relv \hjust{sorted}(\alpha)=\hjust{sorted}(\beta)
\hjust{ for some }\beta\in L\rightset.\cr}$$

Prove or disprove the following statements:
\hline
(1) If $L$ is context-free then sortedsubset$(L)$ is context-free.
\hline
(2) If $L$ is context-free then sorted$(L)$ is context-free.
\hline
(3) If $L$ is context-free then unsorted$(L)$ is context-free.
\par

\problem Context sensitive grammars (15)

Determine the language generated by the following grammar.\ \ (Upper case
letters are nonterminals, lower case letters are terminals, and $S$ is
the start symbol.)
$$\baselineskip14pt\eqalign{S⊗→PABQ\cr
PA⊗→PCT\cr
TA⊗→BCT\cr
TB⊗→BT\cr
CB⊗→BC\cr
TQ⊗→UQ\cr
CU⊗→UB\cr}
\hskip 2cm\eqalign
{BU⊗→VA\cr
BV⊗→VA\cr
PV⊗→PA\cr
PA⊗→aX\cr
XA⊗→aX\cr
XB⊗→bX\cr
XQ⊗→qq\cr}$$
{\sl Hint:} Consider the strings derivable from $PA↑nB↑mQ$.

\vfill\eject
\problem Program Verification (15)

Invent a suitable inductive assertion at point $B$ and prove the following program
partially correct with respect to the given input and output predicates.
Generate and prove all verification conditions.
\par
\vskip 20pt
\hjust to size{\hfill \hjust{A}\hskip 1cm\hfill}
\vskip 5pt
\hjust to size{\hskip 7cm $x>1$ \hfill}
\vskip -29pt
\hjust to size{\hfill\vrule height 40pt\hfill}
\hjust to size{\hfill \boxit{\hjust{$(z,y)←(\hjust{\bf true},2)$}}\hfill}
\vskip 20pt
\hjust to size{\hfill\vjust{\hrule width 4cm}
	\hjust to 4cm{\hskip 5pt\hjust{B}\hfill}\hfill}
\vskip -32pt
\hjust to size{\hfill\vrule height 52pt\hfill}
\hjust to size{\hfill\hskip 3cm
$\left<\!
\vcenter{\vjust to 24pt{\hrule\vfill\hjust{$(y↑2≤x) ∧ z$}\vfill\hrule}}\!\right>
\!\!$\vjust{\hrule width 3cm}\hfill}
\hjust to size{\hfill\vrule height 20pt\hfill}
\hjust to size{\hfill \boxit{\hjust{$z←z∧(x\modop y=0)$}}\hfill}
\hjust to size{\hfill\vrule height 20pt\hfill}
\hjust to size{\hfill \boxit{\hjust{$y←y+1$}}\hfill}
\hjust to size{\hfill\vrule height 20pt\hfill}
\vskip -10pt
\hjust to size{\hfill\vjust{\hrule width 4cm}
	\hskip 4cm\hfill}
\vskip -144pt
\hjust to size{\hfill\vrule height 143pt\hskip 8cm\hfill}
\vskip 10pt
\hjust to size{\hfill\hskip 9cm\hjust{C}\hfill}
\vskip 5pt
\hjust to size{\hskip 7cm$z≡(x\hjust{ is prime})$\hfill}
\vskip -153pt
\hjust to size{\hfill\hskip 8cm\vrule height 147pt\hfill}
\area {Artificial Intelligence}

\problem Theorem proving (3)
 
It has been suggested that work on theorem proving has been
shelved temporarily.  Supposing this is correct, what would be the 
reason for this trend?  State your answer briefly.

\problem Production systems (3)

Comment briefly on the differences between production system
architectures when used for (a) psychological models of cognitive
skills (such as PSG) and (b) expert systems (such as MYCIN or AM).

\problem Quickies (3)

Pick ONE of the pairs of programs listed below and 
contrast the approaches used in the two programs of that pair.  
In light of the superior performance of the "less intelligent" program,
defend the continued use of AI in such problem areas.
\hline
  a)	HEARSAY  - DRAGON
\hline
  b)	CHESS 4.6 [or 4.5 or 4.7] - CAPS
\hline
  c)	INTERNIST [Pople's early version] - MYCIN

\problem Quickies (6)

Order the tasks below by the time it will take to produce
commercial robots to do them.  State the general principles you use to
make the ordering and explain any exceptions.
\hline
	Planning a meal
\hline
	Cooking a meal
\hline
	Serving a meal
\hline
	Teaching arithmetic
\hline
	Teaching soccer
\hline
 	Teaching (about) Shakespeare

\problem AI methods (6)

Briefly define each of the following problem-solving concepts 
and methods, and give a one or two sentence description of the conditions 
under which it is applicable:
\hline
	actors
\hline
	alpha-beta technique
\hline
	British Museum algorithm
\hline
	goal-directed search
\hline
	LISP
\hline
	Simon's ant

\problem Games (11)

Specify a recursive program to solve the following problem:
\hline {\sl
	You and an opponent are facing 11 stacks of pennies, of heights
    11,10,9,...,1.  You will alternate moves, removing pennies, and
    each time someone takes the final penny in a stack his OPPONENT
    will receive one point.  During his turn, each player must remove
    three pennies (three from one pile, two from one pile and one from
    another, or one each from three separate piles).  What should be
    your first move?  (Assume that your opponent will play perfectly,
    that you are trying to maximize the number of points you will
    receive, that your program can have as much time and space as it
    calls for, etc.)}
\hline
In at least two places in the program indicate what kind of 
intelligence would improve the program's performance.  (It is not
necessary to adapt the program to use it, however.)

\problem  AI application (28)

While the issues raised by automation are important 
and difficult, few could dispute the goal of creating an AI program
to replace Howard Cosell.  This question deals with the design
of such a system, a computer program capable of following the action of 
a professional sports event, analyzing it, and reporting its analyses.
\bline
\noindent
(a) [5 points]  A priori, what aspects of a sport would you expect to make this
problem more/less difficult?  Based on this, select a sport (if you
truly are unfamiliar with all professional sports, you may choose
the task of commentator for a chess match).   Justify your choice.
\bline
\noindent
(b) [11 points] What kinds of information could be utilized by such a program,
to enable -- or merely facilitate -- its operation?  For each type,
indicate an appropriate representation (and/or data structure), a
rough estimate of the amount of information desirable, the difficulty
of obtaining it, and its value to the program.
\bline
\noindent
(c) [8 points]  Sketch the flow of control through the program.  Note how 
each type of knowledge mentioned in (b) above is accessed and used.
\bline
\noindent
(d) [4 points]  What are the pros and cons of taking such a knowledge-based 
approach?  Consider, e.g., changing the program to another sport, time/space
costs, debugging the system initially, etc.

\area {Systems}

\problem Compilers runtime organization (15)

Suppose you are writing an Algol compiler for some machine whose
instruction set you know.  Sketch how you would implement run-time
display management on this machine.  Where would you store the stack
pointer, display pointers, and other necessary information?  What
would a stack frame look like?

\problem One-pass, Multi-pass compilers (5)

\noindent
(a) What are the advantages of multi-pass compilers over one-pass compilers?
\bline
\noindent
(b) Describe a way to handle code generation for forward jumps in a one-pass
compiler for the generation of code in-core and for the generation of 
relocatable code on a file.
 
\problem  Exponentiation (8)

\noindent
(a)[6 points]
Pascal is sometimes criticized for lacking an exponentiation operator.
	Suppose you intended to add this operator (denoted **) to the language.  
	Define precisely the meaning of a**b, where a and b are integer or real
	expressions.  When will a**b be illegal (undefined)?  What will be its
	type and value when it is legal?  There is no single answer:  try to
	make reasonable choices.
\bline
\noindent
(b) [2 points]
Based on your answer above, does the usefulness of the exponentiation
operator justify the complexity it entails?

\problem Parameter passing (12)

	Suppose you are given a compiler for an Algol-like language. The
language does not allow to specify in which way parameters are to be passed but
you know that the compiler uses the same mechanism for all parameter types.
Write one or more program fragments to determine whether parameter passing is
\hline
--- call by value
\hline
--- call by value result
\hline
--- call by reference
\hline
--- call by name.
\hline
indicate how the answer can be derived from the result of your program.

\problem Bankers Algorithm (5)

What is the purpose of the Banker's Algorithm?  What information does it
require?
\bline

\problem P/V Multiple (15)

$P2$ and $V2$ are two synchronisation operations analogous
to $P$ and $V$ which use two semaphores simultaneously.  That is, a process
executing $P2(S↓1,S↓2)$ will be delayed until $S↓1$ and $S↓2$ are both $>0$.
At this point $S↓1$ and $S↓2$ are decremented by one and the process can proceed.
$V2(S↓1,S↓2)$ causes $S↓1$ and $S↓2$ to be incremented by one.

Given an implementation of the two operations $P2$ and $V2$; you may use
either $P$ and $V$, monitors, or conditional critical regions.
\area {Hardware}

\problem Logic design (33)

\noindent
(a) [5 points]
Write the state table of the following circuit:
 
	{Diagram of a 4-bit synchronous binary up-counter}
\bline
\noindent
(b) [8 points]
Design a counter with the same state table, minimizing the number of
gates.
\bline
\noindent
(c) [15 points]
Design a synchronous counter with the same state table, using D flip-flops.
\bline
\noindent
(d) [2 points]
Give 2 advantages of synchronous counters over asynchronous ones.
\bline
\noindent
(e) [3 points]
Give three reasons why one combinational circuit may be preferable to
another requiring fewer gates.
 
\problem Logic Technology (7)
 
Briefly describe each of the following logics:
\hline
	RTL
\hline
	MOS
\hline
	ECL
\hline
	TTL
\hline
	Schottky
\hline
	Josephson Junction
\hline
	I$\;$I$\;$L
 
\problem Architecture (15)

\noindent
(a) [1 point]
What is a stack machine?
\bline
\noindent
(b) [1 point]
What is a register machine?
\bline
\noindent
(c) [3 points]
What are each's advantages over the other?
\bline
\noindent
(d) [10 points]
Sketch how you would organize the CPU of a stack machine.  Draw a
block diagram showing the major components and their interconnections.
It should be detailed enough to reveal how the stack is implemented
in terms of other components.
 
\problem Celebrities (5)

Name an accomplishment of each of the following persons:
\hline
	M. Wilkes
\hline
	T. Kilburn
\hline
	S. Cray
\hline
	G. Amdahl
\hline
	G. Bell
\area {Analysis of Algorithms}

\problem Tree traversal (24)

\noindent
(a) [15 points] The non-recursive procedure shown below performs an {\sl inorder}
traversal of a binary tree without using any auxiliary storage.  However,
certain key parts of the procedure have been left out.  You are to fill in
the blanks by figuring out how the algorithm works.

The tree is represented in the usual manner, with each node having
pointers to its left and right sons.  The algorithm works by modifying
certain pointers in the tree and later restoring them.  When the traversal
is completed, the tree has been returned to its original state.
$$
\def\blankbox #1 by #2 {\lower 4pt\hjust{\vrule\vjust{\hrule\hjust to #2
    {\vjust to #1{}}\hrule}\vrule}}
\trace'344 % turn off "overfull box" message
\halign{\hskip20 pt
\hjust to 20pt{\hjust{#}}
⊗\hjust to 20pt{\hjust{#}}
⊗\hjust to 20pt{\hjust{#}}
⊗\hjust to 20pt{\hjust{#}}
⊗\hjust to 20pt{\hjust{#}}\cr
$t ← root;$\cr
{\bf while} $t ≠ \Lambda$ {\bf do begin}\cr
⊗{\bf if} $left(t) = \Lambda$ {\bf then begin}\cr
⊗⊗$visit(t);\  t ←$ \blankbox 14pt by 50pt \cr
⊗{\bf end}\cr
⊗{\bf else begin}\cr
⊗⊗$p ← left(t);$\cr
⊗⊗{\bf comment} $p$ is a temporary variable used only in this block;\cr
⊗⊗{\bf while} $right(p) ≠ \Lambda$ {\bf and} $right(p) ≠$ \blankbox 14pt by 50pt \cr
⊗⊗⊗{\bf do} $p ← right(p);$\cr
⊗⊗{\bf if} $right(p) = \Lambda$ {\bf then begin}\cr
⊗⊗⊗{\bf comment} modify tree link to "remember our place";\cr
⊗⊗⊗$right (p) ← t;\  t ← left(t)$\cr
⊗⊗{\bf end}\cr
⊗⊗{\bf else begin}\cr
⊗⊗⊗$visit(t);$\cr
⊗⊗⊗{\bf comment} fix up tree link;\cr
⊗⊗⊗$right(p) ←$ \blankbox 14pt by 50pt $\,;\  t ←$ \blankbox 14pt by 50pt \cr
⊗⊗{\bf end}\cr
⊗{\bf end}\cr
{\bf end};\cr}$$
\trace'345
\bline
\noindent
(b) [9 points] Now modify the above procedure so that it performs a {\sl preorder}
traversal of the tree.  Try to make as few changes as possible.

\problem Data structures (20)

For each of the situations described below, you are to design a data
structure to represent the set of values so that the indicated operations
can be performed quickly.  You should briefly describe how the operations
are to be performed using your data structure, and estimate the running
time.
\bline
\noindent
(a) We are given a set of numbers, and we want to perform the following
operations:
\hline
\indent (1) Add a number to the set, where this number is
known to be larger than all of the numbers currently in the set.
\hline
\indent (2) Delete the smallest number from the set.
\hline
\indent (3) Delete the {\sl median} number from the set.  (I.e.,
if there are $n$ numbers currently in the set, delete the 
$\lfloor n/2 \rfloor\,$th smallest number.)
\bline
For parts (b), (c), and (d), consider the following situation.  We have
a supply of jars with specified capacities.  We want to perform the
following operations:
\hline
\indent (1) Add a new jar of a specified capacity to our supply.
\hline
\indent (2) Given a volume of liquid, find the {\sl smallest}
jar which can hold this volume.  This jar is then deleted from our supply.
\hline
\noindent Answer the question for each of the following cases:
\bline
\noindent
(b) Jar capacities and liquid volumes are real numbers $\in [1,50]$.
\bline
\noindent
(c) Jar capacities are real numbers; liquid volumes are integers $\in [1,50]$.
\bline
\noindent
(d) Jar capacities are integers $\in [1,50]$; liquid volumes are real numbers.

\problem Register allocation (16)
\dispskip 8pt
\:t=cmtt
\def\tt#1{{\:t #1}}
\rm
Consider a hypothetical computer with the following instructions:
$$\halign{{\:t \lft{\hskip 40pt #}}⊗\lft{\hskip 10pt #}\cr
ri ← m			⊗load register \tt{i} from memory location \tt{m}\cr
ri ← ri $\circ$ m	⊗register \tt{i} gets the result of \tt{ri} $\circ$ \tt{m}\cr
ri ← ri $\circ$ rj	⊗register \tt{i} gets the result of \tt{ri} $\circ$ \tt{rj}\cr}$$
where $\circ$ is a binary operation.
\bline
\noindent
(a) [12 points] 
Suppose we are given a parenthesized expression involving only distinct 
variables (memory locations) and the operator $\circ$, e.g.\
$$((a \circ b) \circ c) \circ (d \circ ((e \circ f) \circ g)).$$
We want to determine the {\sl minimum} number of registers that are needed to
compute the value of this expression.

Since the variables are distinct, you need not worry about common
subexpressions.  You may use commutativity of the operator $\circ$, but do
not assume associativity.  Also, assume that the computer has an infinite
number of registers, whose contents are initially undefined.

Give a formula for the minimum number of registers required by a given
expression, and explain how the computation should be arranged to achieve
this minimum number.  You may introduce any additional notions that are
appropriate. 
\bline
\noindent
(b)[4 points] Now assume that the machine has only $k$ registers.
What is the length (number of operations) of the shortest expression that
cannot be computed by this machine? 
\area {Numerical Analysis}

\problem Stable Algorithms, well-conditioned Problems (21)

	In numerical computation, it is important to distinguish between an
ill-conditioned problem and an unstable algorithm.  In general, a problem
is {\sl ill-conditioned} 
if a small change in the data defining the problem results
in a large change in the solution.  An algorithm is {\sl numerically unstable} if
it introduces large errors in the computed solutions to problems which are
not ill-conditioned.  Note that conditioning is a property of the problem
itself and that stability is a property of the particular method used to
solve the problem.  Here is a list of common numerical problems and possible
methods for solving them.  For each case, choose one of the following which
comes closest to describing the situation.  Explain your conclusions by
providing examples, pointing to error analyses, etc.

	``Good-good'':	Well-conditioned problem and stable algorithm.

	''Good-bad'':	Well-conditioned problem and unstable algorithm.

	``Bad-good'':	Ill-conditioned problem and stable algorithm.

	``Bad-bad'':	Ill-conditioned problem and unstable algorithm.
\bline
\noindent
(a)	Integration of a smooth function $f(x)$ over $[0,1]$ using Simpson's
rule with equally spaced points.
\bline
\noindent
(b)	Differentiation of the same function using finite differences with
equally spaced points.
\bline
\noindent
(c)	Computation of the roots of $f(x)=x↑5-5x↑4+9x↑3-7x↑2+2x$ using
Newton's method. Note that $f(x)=x(x-1)↑3(x-2)$.
\bline
\noindent
(d) Inversion of the matrix

$$A=\left(\vcenter{
	\halign{$\ctr{#}$\quad
 	⊗$\ctr{#}$\cr
	.0001⊗1\cr
	1⊗2\cr}}\right)$$

using Gaussian elimination with no pivoting.
\bline
\noindent
(e) Inversion of the same matrix using Gaussian elimination with partial pivoting.
\bline
\noindent
(f) Inversion of the positive definite matrix

$$A=\left(\vcenter{
	\halign{$\ctr{#}$\quad
 	⊗$\ctr{#}$\cr
	1/19⊗1/18\cr
	1/18⊗1/17\cr}}\right)$$

using Gaussian elimination with no pivoting.
\bline
\noindent
(g) Inversion of the same positive definite matrix using Gaussian elimination
with complete pivoting.


\problem One-sided finite-difference approximation (15)

\noindent
(a)	Find coefficients $\alpha$, $\beta$, and $\gamma$ so that
$$y' = \alpha f(x) + \beta f(x+h) + \gamma f(x+2h)$$
is a good approximation to the first derivative $f'(x)$.
Note that this is a ``one-sided'' approximation because no values of $f$
to the left of $x$ are used. Make whatever smoothness assumptions you think
appropriate.
\bline
\noindent
(b)	Obtain an error bound of the form
$$\leftv y' - f'(x)\rightv ≤ ch↑k.$$

What are $c$ and $k$?
\bline
\noindent
(c)	How small must $h$ be in order that this formula can be used to compute
$\cos (x)$ to four places of accuracy from a table of $\sin (x)$?

\problem Decomposition of a Matrix (8)

	Exercise 9.8 in Forsythe and Moler, Computer Solution of Linear
Algebraic Systems, asks for a proof of the following ``theorem''.
\par
Any symmetric, nonsingular matrix A can be expressed as a product
$$A = LDL↑T$$
where $L$ is a lower triangular matrix with positive diagonal elements, $L↑T$
is its transpose, and $D$ is a diagonal matrix with 
$\pm 1$
on the diagonal.

\bline
\noindent
(a)	Show by means of a simple counterexample that this ``theorem'' is false.
\bline
\noindent
(b)	What additional hypothesis on A would make the statement valid?
(A hypothesis less strict than positive definiteness is possible.)

\problem Representation of floating point numbers (8)

	A new minicomputer, the Avon 9000, has an unorthodox arithmetic unit.
When the following problem is executed, the operating system signals a
division by zero.  What base is used for the representation of floating
point numbers in the Avon 9000 firmware?

$$\eqalign
{⊗\hjust{begin}\cr
⊗\quad\quad H := 1.0/2.0\cr
⊗\quad\quad X := 2.0/3.0 - H\cr
⊗\quad\quad Y := 3.0/5.0 - H\cr
⊗\quad\quad E := (X+X+X) - H\cr
⊗\quad\quad F := (Y+Y+Y+Y+Y) - H\cr
⊗\quad\quad Q := F/E\cr
⊗\quad\quad \hjust{print }Q\cr
⊗\hjust{end}\cr
}$$

\problem p-norm (8)
		
	The p-norm of a vector $x$ is defined for $1 ≤ p < ∞$ by
$$\leftvv x\rightvv↓p=\biglp\sum↓i\leftv x↓i\rightv↑p\bigrp↑{1/p}.$$
\bline
\noindent
(a)	What is
$$\hjust{lim}↓{p→∞}\leftvv x\rightvv↓p\quad?$$
(No proof required.)
\bline
\noindent
(b)	What is the purpose of the restriction $1 ≤ p$?

\bline
\noindent
(c)	What difficulty with floating-point arithmetic might
be encountered in a subroutine or procedure
that computes the p-norm of a vector by directly implementing the definition?

\par\vfill\eject
\end